#include <bits/stdc++.h>
using namespace std;

/*
679. 24 点游戏
已解答
困难
相关标签
premium lock icon
相关企业
给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法，而不是整数除法。
例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起
例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。
如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

 

示例 1:

输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24
示例 2:

输入: cards = [1, 2, 1, 2]
输出: false
 

提示:

cards.length == 4
1 <= cards[i] <= 9
*/

// 法一
class Solution {
public:
    // 主函数：判断给定的4张牌能否通过加减乘除运算得到24
    bool judgePoint24(vector<int>& cards) {
        // 将整数卡牌转换为双精度浮点数，避免除法运算中的整数截断问题
        vector<double> ans;
        for (int card : cards)  ans.push_back(static_cast<double>(card));
        // 调用递归辅助函数求解
        return helper(ans);
    }

    // 递归辅助函数：尝试对当前数字集合进行所有可能的运算组合，判断能否得到24
    // nums：当前参与运算的数字集合
    bool helper(vector<double>& nums) {
        // 递归终止条件：当集合中只剩一个数字时，检查该数字是否接近24（考虑浮点数精度误差）
        if (nums.size() == 1)       return abs(nums[0] - 24) < 1e-6;
        
        // 遍历所有可能的两个不同数字（i和j为两个数字的索引，i≠j）
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i == j) continue;  // 跳过相同索引（同一数字不能重复使用）

                // 构建新的数字集合：包含除了i和j之外的所有数字
                vector<double> answ;
                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j)   answ.push_back(nums[k]);
                }

                // 取出选中的两个数字a和b
                double a = nums[i], b = nums[j];
                
                // 尝试加法：a + b，将结果加入新集合并递归检查
                answ.push_back(a + b);
                if (helper(answ)) return true;  // 若递归返回true，说明找到解
                answ.pop_back();  // 回溯：移除当前运算结果，尝试下一种运算
                
                // 尝试减法：a - b
                answ.push_back(a - b);
                if (helper(answ)) return true;
                answ.pop_back();
                
                // 尝试减法：b - a（减法不满足交换律，需单独尝试）
                answ.push_back(b - a);
                if (helper(answ)) return true;
                answ.pop_back();
                
                // 尝试乘法：a * b
                answ.push_back(a * b);
                if (helper(answ)) return true;
                answ.pop_back();
                
                // 尝试除法：a / b（需保证除数b不为0，避免运行时错误）
                if (b != 0) {
                    answ.push_back(a / b);
                    if (helper(answ)) return true;
                    answ.pop_back();
                }
                
                // 尝试除法：b / a（除法不满足交换律，且需保证除数a不为0）
                if (a != 0) {
                    answ.push_back(b / a);
                    if (helper(answ)) return true;
                    answ.pop_back();
                }
            }
        }
        
        // 所有可能的运算组合都尝试过，无法得到24
        return false;
    }
};

// 法二
class Solution {
public:
    bool judgePoint24(vector<int>& cards) {
        // 转换类型 便于除法计算
        vector<double> unused = vector<double>(cards.begin(), cards.end());
        // 调用递归函数求解
        return point24(unused);
    }

    // 尝试对当前未使用的数字进行所有可能的运算组合，判断能否得到24
    bool point24(vector<double>& unused) {
        int n = unused.size();
        
        // 递归终止条件：当只剩2个数字时，检查所有可能的运算是否能得到24
        if (n == 2) {
            if (almostEqual(unused[0] + unused[1], 24)) return true;  // 加法
            if (almostEqual(unused[0] - unused[1], 24)) return true;  // 减法（第一个减第二个）
            if (almostEqual(unused[1] - unused[0], 24)) return true;  // 减法（第二个减第一个）
            if (almostEqual(unused[0] * unused[1], 24)) return true;  // 乘法
            if (almostEqual(unused[0] / unused[1], 24)) return true;  // 除法（第一个除以第二个）
            if (almostEqual(unused[1] / unused[0], 24)) return true;  // 除法（第二个除以第一个）
            return false;  // 2个数字的所有运算都得不到24
        }
        // 递归过程：当剩余数字多于2个时，任选两个数字进行运算，将结果与其余数字组成新的集合继续递归
        // 遍历所有可能的两个数字组合（i和j，i < j避免重复组合）
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                // 构建新的未使用数字集合：包含当前两个数字的运算结果 + 其余未选中的数字
                vector<double> t = {0};  // t[0]用于存储当前两个数字的运算结果
                // 将除了i和j之外的数字加入新集合
                for (int k = 0; k < n; ++k) {
                    if (k != i && k != j) t.push_back(unused[k]);
                }
                
                // 尝试所有可能的运算，并递归检查新集合能否得到24
                t[0] = unused[i] + unused[j];  // 加法
                if (point24(t)) return true;
                t[0] = unused[i] - unused[j];  // 减法（i - j）
                if (point24(t)) return true;           
                t[0] = unused[j] - unused[i];  // 减法（j - i）
                if (point24(t)) return true;
                t[0] = unused[i] * unused[j];  // 乘法
                if (point24(t)) return true;
                t[0] = unused[i] / unused[j];  // 除法（i / j）
                if (point24(t)) return true;
                t[0] = unused[j] / unused[i];  // 除法（j / i）
                if (point24(t)) return true;
            }
        }
        
        // 所有可能的组合都尝试过，无法得到24
        return false;
    }

    // 判断双精度数a是否近似等于整数b（处理浮点数运算精度误差）
    // eps：允许的误差范围，默认为1e-9
    bool almostEqual(double a, int b, double eps = 1e-9) {
        return fabs(a - b) < eps;
    }
};

// 法三
class Solution {
public:
    bool judgePoint24(vector<int>& cards) {
        // 转换为double，避免除法精度问题
        vector<double> nums;
        for (int c : cards)
            nums.push_back((double)c);
        return dfs(nums);
    }

private:
    // 递归函数：判断当前数字集合能否通过运算得到24
    bool dfs(vector<double>& nums) {
        int n = nums.size();
        // 终止条件1：只剩1个数字，检查是否接近24（应对中间步骤递归到1个数字的情况）
        if (n == 1)
            return abs(nums[0] - 24) < 1e-6;

        // 终止条件2：只剩2个数字，直接检查所有运算是否得24（提前终止，减少递归深度）
        if (n == 2) {
            double a = nums[0], b = nums[1];
            return (abs(a + b - 24) < 1e-6) || (abs(a - b - 24) < 1e-6) ||
                   (abs(b - a - 24) < 1e-6) || (abs(a * b - 24) < 1e-6) ||
                   (b != 0 && abs(a / b - 24) < 1e-6) ||
                   (a != 0 && abs(b / a - 24) < 1e-6);
        }

        // 只选择i < j的组合，避免重复处理同一对数字（核心优化）
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                double a = nums[i], b = nums[j];
                // 收集除i和j外的剩余数字
                vector<double> rest;
                for (int k = 0; k < n; ++k) {
                    if (k != i && k != j)
                        rest.push_back(nums[k]);
                }

                // 尝试所有可能的运算，将结果与剩余数字组合后递归
                // 1. 加法（a + b）
                rest.push_back(a + b);
                if (dfs(rest))
                    return true;
                rest.pop_back(); // 回溯

                // 2. 减法（a - b）
                rest.push_back(a - b);
                if (dfs(rest))
                    return true;
                rest.pop_back();

                // 3. 减法（b - a）
                rest.push_back(b - a);
                if (dfs(rest))
                    return true;
                rest.pop_back();

                // 4. 乘法（a * b）
                rest.push_back(a * b);
                if (dfs(rest))
                    return true;
                rest.pop_back();

                // 5. 除法（a / b，需保证b不为0）
                if (b != 0) {
                    rest.push_back(a / b);
                    if (dfs(rest))
                        return true;
                    rest.pop_back();
                }

                // 6. 除法（b / a，需保证a不为0）
                if (a != 0) {
                    rest.push_back(b / a);
                    if (dfs(rest))
                        return true;
                    rest.pop_back();
                }
            }
        }

        // 所有组合都尝试过，无法得到24
        return false;
    }
};
